package com.zyk.grate_offer.class04;

import java.util.Arrays;

/**
 * 力扣: https://leetcode-cn.com/problems/interleaving-string/
 *
 * @author zhangsan
 * @date 2021/4/30 10:33
 */
public class Code07_InterLeavingString {

    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        return process(s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), 0, 0);
    }

    // 区间问题
    // 看s1[0~i] + s2[0~j] 是否能组成 target[0~i+j]
    public static boolean process(char[] s1, char[] s2, char[] target, int i, int j) {
        // 考虑, s1 或 s2先匹配完了, 剩下的能否组成target
        if (i == s1.length) {
            for (int k = j; k < s2.length; k++) {
                if (target[i + k] != s2[k]) return false;
            }
            return true;
        }
        if (j == s2.length) {
            for (int k = i; k < s1.length; k++) {
                if (target[j + k] != s1[k]) return false;
            }
            return true;
        }
        // 两种结果:    前提首先这个字符得能匹配上
        // 1. 这个字符s1往后扩,
        // 2. 这个字符s2往后扩,
        boolean p1 = false, p2 = false;
        if (s1[i] == target[i + j]) {
            p1 = process(s1, s2, target, i + 1, j);
        }
        if (s2[j] == target[i + j]) {
            p2 = process(s1, s2, target, i, j + 1);
        }
        return p1 || p2;
    }

    public static boolean isInterleave2(String s1, String s2, String s3) {
        int s1Len, s2Len;
        if ((s1Len = s1.length()) + (s2Len = s2.length()) != s3.length()) return false;
        Boolean[][] dp = new Boolean[s1Len + 1][s2Len + 1];
        boolean ans = process2(s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), 0, 0, dp);

        System.out.println("==============傻缓存: ================");
        for (Boolean[] arr : dp) {
            System.out.println(Arrays.toString(arr));
        }
        return ans;
    }

    // 区间问题
    // 看s1[0~i] + s2[0~j] 是否能组成 target[0~i+j]
    public static boolean process2(char[] s1, char[] s2, char[] target, int i, int j, Boolean[][] dp) {
        if (dp[i][j] != null) return dp[i][j];
        boolean ans = true;
        if (i == s1.length) {
            for (int k = j; k < s2.length; k++) {
                if (target[i + k] != s2[k]) {
                    ans = false;
                    break;
                }
            }
        } else if (j == s2.length) {
            for (int k = i; k < s1.length; k++) {
                if (target[j + k] != s1[k]) {
                    ans = false;
                    break;
                }
            }
        } else {
            ans = false;
            boolean p1 = false, p2 = false;
            if (s1[i] == target[i + j]) {
                p1 = process2(s1, s2, target, i + 1, j, dp);
            }
            if (s2[j] == target[i + j]) {
                p2 = process2(s1, s2, target, i, j + 1, dp);
            }
            ans = p1 || p2;
        }
        return dp[i][j] = ans;
    }

    public static boolean isInterleave3(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();
        if (str3.length != str1.length + str2.length) {
            return false;
        }
        boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
        dp[0][0] = true;
        for (int i = 1; i <= str1.length; i++) {
            if (str1[i - 1] != str3[i - 1]) {
                break;
            }
            dp[i][0] = true;
        }
        for (int j = 1; j <= str2.length; j++) {
            if (str2[j - 1] != str3[j - 1]) {
                break;
            }
            dp[0][j] = true;
        }
        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                if ((str1[i - 1] == str3[i + j - 1] && dp[i - 1][j])
                        || (str2[j - 1] == str3[i + j - 1] && dp[i][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[str1.length][str2.length];
    }

    //for test
    public static void main(String[] args) {
//        String s1 = "aabcc";
//        String s2 = "dbbca";
//        String target = "aadbbcbcac";
        String s1 = "a";
        String s2 = "a";
        String target = "ca";

        System.out.println(isInterleave(s1, s2, target));
        System.out.println(isInterleave2(s1, s2, target));
        System.out.println(isInterleave3(s1, s2, target));
    }

}
